POJ 3666 dp

Posted on | In , ,

给一个长度为 $n$ 的序列 $a$，每次可以对这个序列的任意一个数 $+1$ 或者 $-1$ 代价都是 $1$，问使序列 $a$ 变成(不严格)单调的最小代价。
$n\le2000，a_i\le10^9$

这个题看起来有点难搞啊？
因为很难判断不符合单调的数是把它本身修改掉还是把它前面/后面修改掉更优。

题解

  • 考虑最终的序列每个数肯定是原序列的某个值，但每个位置不能判断是它前面位置数还是后面的数
  • 离散化 a[i]$
  • 定义 $dp[i][j]$：考虑了前 $i$ 个数，且第 $i$ 个数为第 $j$ 大的数的单调的最小值，暴力枚举 $dp[i-1]j$ 转移到 $dp[i][j]$ 的时间复杂度是 $O(n^3)$
  • 考虑优化，$dp[i][j]$若是作为只上升的话，显然大于 $j$ 的都不会影响到 $dp[i][j]$ 的最小值，因为后面的肯定比前面的大。
  • 同理最小可以得出
  • 时间复杂度$O(n^2)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>

using namespace std;
#define ll long long

const int maxn = 2002+10;

int n, a[maxn], b[maxn], c[maxn];
ll dp[maxn][maxn];
ll ans=0;

int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d", &a[i]);
        b[i]=a[i];
    }
    sort(b+1, b+n+1);
    int p=unique(b+1,b+n+1)-b;
    for(int i=1;i<=n;i++)
    {
        ll minx=dp[i-1][1];
        for(int j=1;j<=p-1;j++)
        {
            minx=min(minx, dp[i-1][j]);
            dp[i][j]=minx+abs(b[j]-a[i]);
        }
    }
    ans=dp[n][1];
    for(int i=1;i<=p-1;i++)
        ans=min(ans, dp[n][i]);
    printf("%lld\n", ans);
    return 0;
}